#!/usr/bin/env python

def listcmp(a,b):
    assert(len(a) == len(b))
    for i in range(len(a)):
        if a[i] == "\0":
            return 1
        elif b[i] == "\0":
            return -1
        elif a[i] < b[i]:
            return -1
        elif a[i] > b[i]:
            return 1
    return 0

def printtable(table):
    print "["
    for row in table:
        print "\t", row
    print
    print "]"

def bwt(ss):
    """Apply Burrows-Wheeler transform to input string."""
    s = ss[:]
    assert "\0" not in ss, "Input string cannot contain null character ('\0')"
    s.append("\0") # Add end of file marker
    table = [s[i:] + s[:i] for i in range(len(s))]  # Table of rotations of string
    table.sort(cmp = listcmp)
    #printtable(table)
    last_column = [row[-1] for row in table]  # Last characters of each row
    return last_column
    #return "".join(last_column)  # Convert list of characters into string


def ibwt(r):
    """Apply inverse Burrows-Wheeler transform."""
    table = []
    for i in range(len(r)):  # Make empty table
        table.append([])
    for i in range(len(r)):
        table = [[r[i]] + table[i] for i in range(len(r))]  # Add a column of r
        table.sort(cmp = listcmp)

    s = [row for row in table if row[-1] == "\0"][0]  # Find the correct row (ending in "\0")
    return s[:-1]  # Get rid of trailing null character


if __name__ == "__main__":
    s = ["^", "B", "A", "N", "A", "N" , "A"]
    #s = ["1", "0", "0", "0", "1", "0" , "0", "1", "0", "0", "1"]
    print "s=",s
    c = bwt(s)
    print "bwt:",c
    print "ibwt:", ibwt(c)

    vs = s[:]
    vs.reverse()
    print "vs=", vs
    c = bwt(vs)
    print "bwt:",c
    print "ibwt:", ibwt(c)
    
